This invention relates to the field of meshing, specifically using a computer to generate computer-readable mesh representations of trunk/graft regions for use in, for example, finite element modeling of mechanical systems.
Three-dimensional finite element analysis (FEA) is an important design tool for physicists and engineers. Before the analysis can begin, a mesh needs to be generated on the model. During the last several decades, much research has been devoted to mesh generation. Tetrahedral mesh generators are well developed and many have been implemented in software packages. Hexahedral mesh generators are not as well developed, however, and lack the automation of current tetrahedral mesh generators.
For most applications, hexahedral elements are preferred over tetrahedral elements for meshing 3-D solids. See, e.g., Benzley et al., “A Comparison of All-Hexahedral and All-Tetrahedral Finite Element Meshes for Elastic and Elasto-Plastic Analysis,” Proceedings 4th International Meshing Roundtable, Sandia National Laboratories 95, pp. 179–191 (October 1995); Cifuentes and Kalbag, “A Performance Study of Tetrahedral and Hexahedral Elements in 3-D Finite Element Structural Analysis,” Finite Elements en Analysis and Design, Vol. 12, pp. 313–318 (1992). Unfortunately, a high quality mesh of hexahedral elements can be more difficult to generate. Minimally, the mesh needs to be conformal between adjoining solids and have high quality elements at the bounding surfaces. Because of the constraints on hexahedral elements, automatic generation of high quality hexahedral meshes on arbitrary 3-D solids has proven elusive. See, e.g., Mitchell, “A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume,” Proceedings, 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS '96), Lecture Notes in Computer Science 1046, Springer, pp. 465–476 (1996).
Over the last several years much work has been put into sweeping algorithms. These algorithms can mesh a wide range of 2½-D (prismatic) solids. The sweeping algorithms generally take a 2-D unstructured quadrilateral mesh from the source surface and project it through the volume to the target surface. Sweeping algorithms have matured to handle nonplanar, non-parallel source and target surfaces and variable cross-sectional area as well as multiple source and target surfaces. See, e.g., Staten et al., “BMSweep: Locating Interior Nodes During Sweeping,” Proceedings 7th International Meshing Roundtable 98, pp. 7–18 (October 1998); Blacker, “The Cooper Tool,” Proceedings 5th International Meshing Roundtable 96, pp. 13–29 (October 1996); Mingwu and Benzley, “A Multiple Source and Target Sweeping Method for Generating All Hexahedral Finite Element Meshes” Proceedings, 5th International Meshing Roundtable 96, pp. 217–225 (October 1996).
To maintain the structured mesh in the sweep direction, current sweeping algorithms require the linking surfaces (those that connect the source to the target) to be mappable or submappable. This constraint limits the number of solids that can be meshed with these algorithms. They specifically exclude solids with imprints or protrusions on the linking surfaces, a geometry common in many problems. Accordingly, there is a need for new meshing methods that remove this constraint on linking surfaces.